import java.util.Stack;

/*
 * @author zzr
 * @date: 2025/10/14  18:38
 * @description: 输入两个整数序列，第一个序列表示栈的压入顺序
 * 请判断第二个序列是否有可能为该栈的弹出序列
 */
public class Demo18 {
    public boolean IsPopOrder(int[] pushA, int[] popA) {

        Stack<Integer> stack = new Stack<>();

        int j = 0; //遍历 popA 的下标

        for (int i = 0; i < pushA.length; i++) {

            // 遍历 pushA 将 pushA 中的元素入栈
            stack.push(pushA[i]);

            // 注意 stack 可能为空 且 j 可能超出 popA 的长度
            while (!stack.isEmpty() && j < popA.length && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();

    }
}
